package hot;

/**
 * @author way
 * @create 2025-04-02 16:27
 */
public class _518_change {
    public int change(int amount, int[] coins) {
        //使用下标为[0, i]的coins[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种组合方法
        int[][] dp = new int[coins.length][amount + 1];

        //用物品i（即coins[i]） 装满容量为0的背包 有几种组合方法。
        //都有一种方法，即不装。所以 dp[i][0] 都初始化为1
        for (int i = 0; i < coins.length; i++) {
            dp[i][0] = 1;
        }
        //如果 j 可以整除 物品0，那么装满背包就有1种组合方法。
        for (int i = 0; i <= amount; i++) {
            if (i % coins[0] == 0) dp[0][i] = 1;
        }

        for (int i = 1; i < coins.length; i++) {
            for (int j = 0; j <= amount; j++) {
                if (coins[i] > j) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
            }
        }
        return dp[coins.length - 1][amount];
    }
}
